package com.yiwenup.struct._05_unionfind;

/**
 * 并查集：快速查找实现
 * 基于 rank 的 PathCompression 的优化
 * <p>
 * 时间复杂度：find - O(logn)；union - O(logn)
 **/
public class QuickUnionV4 extends QuickUnionV3 {

    public QuickUnionV4(int capacity) {
        super(capacity);
    }

    /**
     * 在 find 的时候，将路径上的元素直接指向【根】节点，这样会使得成本比较高
     */
    @Override
    public int find(int v) {
        rangeCheck(v);

        if (parents[v] != v) {
            parents[v] = find(parents[v]);
        }

        return parents[v];
    }
}
